package wtx.leetcode;

import java.util.*;
import java.util.Random;

// naive solution

public class Solution {
    // brute force solution
    static public int shortestSubarray0(int[] A, int K) {
        if (A == null) {
            return -1;
        }
        final int N = A.length;
        if (N == 0) {
            return -1;
        }
        int shortestPath = N+1;
        int[] range = new int[2];
        for (int i = 0; i < N; ++i) {
            int sum = 0;
            for (int j = i; j >= 0 ; --j) {
                sum += A[j];
                if (sum >= K) {
                    int n = i - j + 1;
                    if (shortestPath > n) {
                        shortestPath = n;
                        range[0] = j;
                        range[1] = i;
                    }
                }
            }
        }
//        System.out.println(String.format("from %d to %d", range[0], range[1]));
        return shortestPath <= N ? shortestPath : -1;
    }
    class MinInfo {
        int minimum, secmin;
        int minpos, secminpos;
        void init() {
            minimum = secmin = Integer.MAX_VALUE;
            minpos = secminpos = -1;
        }
        MinInfo() {
            init();
        }
        boolean checkSetMin(int v, int p) {
            if (v < minimum) {
                secmin = Integer.MAX_VALUE;
                secminpos = -1;
                minimum = v;
                minpos = p;
                return true;
            } else {
                return false;
            }
        }
        boolean checkSetSecMin(int v, int p) {
            if (v < secmin) {
                secmin = v;
                secminpos = p;
                return true;
            } else {
                return false;
            }
        }
        void updateMin(int v, int p) {
            if (!checkSetMin(v, p)) {
                checkSetSecMin(v, p);
            }
        }
    }
    public int shortestSubarray(int[] A, int K) {
        if (A == null) {
            return -1;
        }
        final int N = A.length;
        if (N == 0) {
            return -1;
        }
        int i = 0, j = 0;
        int shortestPath = N+1;
        MinInfo minPos = new MinInfo();
        int sum = 0;
        for (;i < N; ++i) {
            if (A[i] >= K) {
                return 1;
            }
            sum += A[i];
            minPos.updateMin(sum, i);
            if (sum < 0) {
                sum = 0;
                j = i + 1;
                minPos.init();
            } else {
                if (sum >= K) {
                    if (sum - minPos.minimum >= K) {
                        if (minPos.secminpos > 0 && sum - minPos.secmin >= K) {
                            int t = minPos.secminpos;
                            j = t+1;
                            sum -= minPos.secmin;
                            while (j <= i) {
                                if (sum >= K) {
                                    t = j;
                                    int n = i - j + 1;
                                    if (n < shortestPath) {
                                        shortestPath = n;
                                    }
                                }
                                sum -= A[j++];
                            }
                            // revert back, violate O(n)
                            j = t + 1;
                        } else {
                            // no second element
                            j = minPos.minpos + 1;
                            int n = i - j + 1;
                            if (n < shortestPath) {
                                shortestPath = n;
                            }
                            ++j;
                        }
                    } else {
                        int n = i - j + 1;
                        if (n < shortestPath) {
                            shortestPath = n;
                        }
                        ++j ;
                    }
                    i = j - 1;
                    sum = 0;
                    minPos.init();
                }
            }
        }
        return shortestPath <= N ? shortestPath : -1;
    }
    public static void main(String[] args) {
        Random rnd = new Random(1263);

        for (int n = 0; n < 100; ++n) {
            final int arrayLen = rnd.nextInt(200) + 10;
            int[] array = new int[arrayLen];
            StringJoiner sj = new StringJoiner(",", "[", "]");
            for (int k = 0; k < arrayLen; ++k) {
                int c = rnd.nextInt(100) - 50;
                array[k] = c;
                sj.add("" + c);
            }
            Solution s = new Solution();
            int k = rnd.nextInt(arrayLen / 4 * 20) + 30;
            int r1 = shortestSubarray0(array, k), r2 = s.shortestSubarray(array, k);
            if (r1 != r2) {
                System.out.println(String.format("array: %s, \nk = %d, min len = [%d, %d]", sj.toString(), k,
                        r1, r2));
            }
        }
    }
}
